This study will determine the effect of recombinant human interleukin-12 (rhIL-12) on HIV-infected subjects with < 50 CD4+ T cells/mL who have no evidence of serious ongoing opportunistic infections but are at risk for AIDS-related disseminated Mycobacterium avium complex (MAC) infection. It will determine the tolerance of a range of chronic subcutaneous rhIL-12 dosing regimens, and characterize their immunologic, antiviral, and potential antimycobacterial effects. In addition, based on the maximum tolerated dose (MTD) of rhIL-12 tolerated by subjects with < 50 CD4+ T cells/mL (Part A), a second group of subjects with 300-500 CD4+ T cells/mL will receive the MTD of rhIL-12 or matching placebo to validate the reliability of the functional immunologic evaluations and assess the in vivo immunologic activity of rhIL-12 in these subjects, who are not profoundly immunosuppressed.